#include<bits/stdc++.h>
#include "graph.h"
using namespace std;
const int N=2e2+5;
const int inf=0x3f3f3f3f;
int n,pos,c[N],d[N][N],dis[N][N],kong[N],lzj[N][N],prt[N],prt_edge[N];
vector<int>rez[N][2];
map<vector<int>,int>Map[2];
void dfs(int x)
{
	int num=NumberOfRoads();
	int last=LastRoad();
	for(int i=1;i<=num;i++)
	{
		if(i==last)continue;
		Move(i,2);
		int color_y=Color();
		int sb=LastRoad();
		if(color_y!=1)
		{
			Move(sb,2);
			continue;
		}
		int y=++pos;
		d[x][y]=d[y][x]=1;
		lzj[x][i]=y;
		prt[y]=x,prt_edge[y]=sb;
		for(auto j:rez[x][0])rez[y][0].push_back(j);//1->y
		rez[y][0].push_back(i);
		
		rez[y][1].push_back(sb);
		for(auto j:rez[x][1])rez[y][1].push_back(j);//y->1
//		cout<<"dfs: "<<x<<' '<<y<<'\n';
		dfs(y);
		Move(sb,2);
	}
}
void dfs_color(int x,int now)
{
	c[x]=now+1;
	int num=NumberOfRoads();
	for(int i=1;i<=num;i++)
	{
		if(!lzj[x][i])continue;
		int y=lzj[x][i];
		Move(i,c[x]);
		int tmp=(now+1)%3;
		dfs_color(y,tmp);
		Move(prt_edge[y],c[y]);
	}
}
void Dfs(int x)
{
	int num=NumberOfRoads();
	for(int i=1;i<=num;i++)
	{
		if(i==prt_edge[x])continue;
		if(!lzj[x][i])
		{
//			cout<<"wtf: "<<x<<' '<<i<<'\n';
			Move(i,2);
			int tmp=LastRoad();
			Move(tmp,3);
			int p=x;
			vector<int>g;
			while(1)
			{
				int color=Color();
				if(color==3)d[x][p]=d[p][x]=1;
				if(p==1)break;
//				cout<<"sb: "<<p<<' '<<prt_edge[p]<<'\n';
				Move(prt_edge[p],2);
//				cout<<"last: "<<LastRoad()<<'\n';
				g.push_back(LastRoad());
				p=prt[p];
			}
			if(g.size())for(int j=g.size()-1;j>=0;j--)Move(g[j],2);
			Move(i,2);
			tmp=LastRoad();
			Move(tmp,2);
			continue;
		}
		int y=lzj[x][i];
		Move(i,2);
		Dfs(y);
		Move(prt_edge[y],2);
	}
}
void prepare()
{
	++pos;
	dfs(1);
	n=pos;
	for(int i=1;i<=n;i++)Map[0][rez[i][0]]=i,Map[1][rez[i][1]]=i;
}
void solve()
{
	Dfs(1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)dis[i][j]=inf;
		dis[i][i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(d[i][j])dis[i][j]=d[i][j];
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			kong[dis[i][j]]++;
		}
	}
}
void Inspect(int R)
{
	prepare();
	solve();
	for(int i=1;i<=R;i++)kong[i]=kong[i]/2;
	for(int i=1;i<=R;i++)Answer(i,kong[i]);
}
/*
4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0
*/
